1. Field of the Invention
The present invention relates to database queries, particularly to the execution efficiency of database query statements, and more specifically to a translation system and method for SPARQL queries.
2. Description of the Related Art
In recent years, the success of relational database management systems (R-DBMS) has brought volumes of data in horizontal schemas. With the increased use of ontology in various applications, supporting RDF (Resource Description Framework) query against legacy R-DBMS has gained attention from both relational database and semantic web communities. On one hand, representing relational data as RDF graphs provides unified access to different sources for information federation and integration. On the other hand, exposing a large amount of data locked in relational databases can enrich content on the semantic web.
FIG. 1 shows a structural block diagram of a virtual RDF store. At the client, a query is made using SPARQL (Simple Protocol and RDF Query Language), and a query engine translates SPARQL statements into SQL statements using a D2R (Database to Relational database) mapping unit so as to query the relational database.
SPARQL is recommended by the W3C (World Wide Web Consortium) for RDF query language and is a query language and data acquisition protocol developed for RDF. The building blocks of SPARQL include the following clauses:                Triple: <subject predicate object> (abbr. <s p o>)        “AND” Pattern: <s p o> <s p o>        “OR” Pattern: <s p o> UNION <s p o>        Filter conditions: Filter (conditions)        
Typically, semantic queries can be divided into two categories, i.e. positive semantic queries and negative semantic queries. For example, in order to find all items A that are white in color in a store, a simple positive SPARQL query can be made as follows:<?x typeof item A><?x color white>
To find all items A that are not white in the store, the following query can be made:<?x typeof type A item>!<?x color white>  (1),where “!” represents logical “Not”. The symbol “!” is only an example, and those skilled in the art should appreciate that, any representation capable of expressing “Not” logic is feasible. However, all syntax patterns in the existing SPARQL language are expressed in positive forms and there is not such a syntax structure as “!<s p o>”, that is, direct queries in negative patterns are not supported, structure like “!<?x color white>” in the expression (1) is not supported.
As another example, assume a search is desired for two products that can be sold as a bundle via a third product but cannot be directly sold as a bundle, and neither of which can be sold as a bundle individually. Assume that the bundle-sale conditions of articles in a certain store are as follows
(we use “-” to denote bundle-sale relationship):
                (a) item B-item A, item A-item C;        (b) item B-item D, item D-item E, item B-item E.Assuming that item B and item C cannot be sold as a bundle, but they can be sold through a bundle via item A. Then, if a query is made according to the following expression (2),Select?x,?z where {<?x BundleSale?y><?y BundleSale?z>!<?x BundleSale?z>!<?x BundleSale?x>}  (2),a result of the query will be (a).        
From the above, it follows that a query in an explicit negative pattern such as “!<s p o>” is quite useful. However, there are no syntax structures of an explicit negative pattern in the existing SPARQL language.
Thus, in the prior art, negative patterns are indirectly expressed in a positive way in the existing SPARQL language, which is abstracted as a relational algebra formula P1!P2=P1−P1P2, where “P1P2” represents two triples combined using an “AND” logic, called a hidden negative pattern. For example, the query in the expression (1) can be expressed in the following form:Select?x where {<?x typeof item A><?y typeof item A><?y color white>Filter(?x!=?y)}
As another example, the query in the expression (2) can be expressed in the following form:Select?x,?z where {<?x BundleSale?y><?y BundleSale?z><?m BundleSale?o><?o BundleSale?n><?m BundleSale?n><?a BundleSale?b><?b BundleSale?c><?a BundleSale?a>Filter((?x!=?m OR ?z !=?n)OR(?x!=?a OR?z!=?c))}
However, in a practical operational process of compiling the above-mentioned hidden negative pattern into an SQL statement, the unequal condition “?x!=?y” will yield many unnecessary JOIN operations, thus incurring high space costs. In addition, the “!=” operation may be very complicated in the translated SQL statement. Moreover, the unequal condition will be translated into a combination of several positive assertions and several negative assertions, thus increasing computation cost. In summary, the existing SPARQL queries cannot support full semantic queries, and the existing systems and methods for translation of SPARQL into SQL do not perform efficiently.